1. Field
This application relates generally to techniques for scheduling computational processes and, more specifically, to scheduling computational processes for computer-generated animations.
2. Description of the Related Art
Computer animation is the process of generating animated images using computer graphics. FIG. 1 depicts an example of a computer-generated image. A computer-generated scene may include a virtual environment including various objects (e.g., trees, rocks, clouds, etc.) and characters (e.g., animals, people, etc.). Models of characters, for example, may be created and then moved or deformed to simulate motion. Images of the scene are rendered at selected times or frames to create an animated video.
The computer animation processes can be computationally demanding in terms of the number of computations and the amount of computer memory required. The computational resources required to store the data underlying the environment, objects, and characters and to generate a video depend on various factors including the number and size of the characters being animated, the resolution of the characters, the resolution of the rendered images, and the complexity of the models used to determine character motion.
For even moderately complex animations, many personal electronic devices, such as smartphones and tablets, may lack the processing and memory resources necessary to produce video-quality animations in real-time (e.g., to produce computer-generated images with 720p or 1080p resolution at approximately 24-30 frames per second (fps)). For example, a smartphone is unlikely to have enough processors with sufficient speed to generate a new image every 33 milliseconds (ms) (i.e., the frame time of a 30 fps video). Furthermore, even a typical personal computer is unlikely to have the memory capacity required to store the underlying data of complex virtual characters and scenes, or the processing power to generate a video-quality animation in real time.
One potential solution to this problem is to use a remote machine to store the data and perform the animation processing as a service, and then deliver the output to a client device. However, even if the resources for animation are located remotely, there is still a need to allocate processing resources such that an acceptable quality of service is provided.
Quality of service may be defined at least in part by the frame rate of the video, resolution of the rendered video, or resolution of the computer-generated environment and characters. Quality of service may also depend on the percentage of rendered frames that are fully updated such that the rendered image appears as it would if unlimited resources were available. Some users may prefer a fully updated image at every frame at the cost of a slower frame rate or temporary interruptions while the image is being updated or buffered. Temporary interruptions result in a slower effective frame rate. Other users may prefer a faster frame rate without interruptions, at the cost of occasionally receiving a partially updated or non-updated image at each frame. Some users may also be willing to sacrifice frame rate or tolerate interruptions for images with higher resolution.
Maintaining an acceptable quality of service may be manageable in some situations. For example, if the parameters of the scene (e.g., the number, resolution, and motions of the characters in the scene) are not very demanding or are known in advance, the computations required to generate images can be determined in advance and sufficient resources may be allocated to perform the computations at a reliable rate. The computations may be configured based in part on the inputs required by each computation. For example, if computation B requires data produced by computation A, then computation A is scheduled to occur before computation B. Furthermore, an event-driven scheme may be implemented in which computation B is triggered by the completion of computation A. Thus, computation B waits to start until computation A has completed, thus ensuring that computation B will always have the data it requires.
An event-driven system, however, may be unable to achieve a desired frame rate if one or more computations take longer than expected. If a computation does not complete on time, all subsequent computations are delayed. Moreover, the delay experienced by downstream computations is compounded as more computations exceed their estimated duration. If the delay is large enough, an event-driven scheduling scheme may fail to meet some aspect of the quality of service, such as frame rate.
Maintaining a desired quality of service with an event-driven schedule may be even more difficult for applications in which the parameters of a scene are not predetermined and the exact amount of resources that will be required at any particular time is unknown. In an interactive system, for example, a user may be able to provide real-time input that affects the animation. Since the animation cannot be predetermined, the system has to generate imagery in response to the user input. Not only does the system have to generate images on-the-fly, but it also may require additional resources to process the user input and determine the appropriate response. The uncertainty in the resources that may be required to meet a particular quality of service becomes even greater if the system allows an unknown number of users to demand resources at the same time.
A system with uncertain demand could be designed to meet the desired quality of service at the maximum expected load. However, this would likely be inefficient as it could leave a large portion of available resources unused a majority of the time.
Thus, there is an opportunity to develop techniques to allocate and consume computational resources to generate real-time computer-generated imagery with a reliable quality of service.